076. 数组中的第 k 大的数字

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1：

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2：

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

答案

sort API

思路：

1. 先倒序排序
2. slice 获取目标值：slice(k-1,k)[0]

let arr = [3,2,1,5,6,4]
const k = 2

var findKthLargest = function(arr, k) {
  return arr.sort((a,b)=>b-a).slice(k-1,k)[0]
}

console.log(findKthLargest(arr,k))

快速排序

let arr = [3,2,1,5,6,4]
const k = 2

function quickSort(arr){
  if(arr.length <=1)return arr

  let pivotIndex = Math.floor(arr.length/2)
  let pivot = arr.splice(pivotIndex,1)[0]

  let left = []
  let right = []

  for(let i=0;i<arr.length;i++){
    if(arr[i] > pivot){
      left.push(arr[i])
    }else{
      right.push(arr[i])
    }
  }

  return quickSort(left).concat([pivot],quickSort(right))
}

var findKthLargest = function(arr, k) {
  const sortArr = quickSort(arr)
  return sortArr.slice(k-1,k)[0]

}

console.log(findKthLargest(arr,k))